From 080e62509029418aa83bd4a5f8cd136c4df7ec94 Mon Sep 17 00:00:00 2001
From: Benjamin Otte <otte@redhat.com>
Date: Tue, 21 Jul 2020 01:40:06 +0200
Subject: [PATCH] sortlistmodel: Make the sort callback useful

1. Run step() for a while to avoid very short steps
   This way, we batch items-changed() emissions.

2. Track the change region accurately
   This way, we can avoid invalidating the whole list if our step just
   touched a small part of a huge list.
   As this is a merge sort, this is a common occurence when we're buys
   merging chunks: The rest of the model outside those chunks isn't
   changed.

Note that the tracking is accurate: It determines the minimum change
region in the model.

This will be important, because the testsuite is going to test this.
---
 gtk/gtksortlistmodel.c | 58 +++++++++++++++++++++++++++++++++++++++---
 1 file changed, 55 insertions(+), 3 deletions(-)

diff --git a/gtk/gtksortlistmodel.c b/gtk/gtksortlistmodel.c
index 52c7afebbb..eed0d8fd52 100644
--- a/gtk/gtksortlistmodel.c
+++ b/gtk/gtksortlistmodel.c
@@ -40,6 +40,16 @@
  */
 #define GTK_SORT_MAX_MERGE_SIZE (1024)
 
+/* Time we spend in the sort callback before returning to the main loop
+ *
+ * Increasing this number will make the callback take longer and potentially
+ * reduce responsiveness of an application, but will increase the amount of
+ * work done per step. And we emit an ::items-changed() signal after every
+ * step, so if we can avoid that, we recuce the overhead in the list widget
+ * and in turn reduce the total sort time.
+ */
+#define GTK_SORT_STEP_TIME_US (1000) /* 1 millisecond */
+
 typedef struct _SortItem SortItem;
 struct _SortItem
 {
@@ -166,15 +176,57 @@ gtk_sort_list_model_stop_sorting (GtkSortListModel *self)
   g_clear_handle_id (&self->sort_cb, g_source_remove);
 }
 
+static gboolean
+gtk_sort_list_model_sort_step (GtkSortListModel *self,
+                               guint            *out_position,
+                               guint            *out_n_items)
+{
+  gint64 end_time = g_get_monotonic_time ();
+  gboolean result = FALSE;
+  GtkTimSortRun change;
+  SortItem *start_change, *end_change;
+
+  end_time += GTK_SORT_STEP_TIME_US;
+  end_change = sort_array_get_data (&self->items);
+  start_change = end_change + sort_array_get_size (&self->items);
+
+  while (gtk_tim_sort_step (&self->sort, &change))
+    {
+      result = TRUE;
+      if (change.len)
+        {
+          start_change = MIN (start_change, (SortItem *) change.base);
+          end_change = MAX (end_change, ((SortItem *) change.base) + change.len);
+        }
+     
+      if (g_get_monotonic_time () >= end_time)
+        break;
+    }
+
+  if (start_change < end_change)
+    {
+      *out_position = start_change - sort_array_get_data (&self->items);
+      *out_n_items = end_change - start_change;
+    }
+  else
+    {
+      *out_position = 0;
+      *out_n_items = 0;
+    }
+
+  return result;
+}
+
 static gboolean
 gtk_sort_list_model_sort_cb (gpointer data)
 {
   GtkSortListModel *self = data;
+  guint pos, n_items;
 
-  if (gtk_tim_sort_step (&self->sort, NULL))
+  if (gtk_sort_list_model_sort_step (self, &pos, &n_items))
     {
-      guint n_items = sort_array_get_size (&self->items);
-      g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, n_items);
+      if (n_items)
+        g_list_model_items_changed (G_LIST_MODEL (self), pos, n_items, n_items);
       return G_SOURCE_CONTINUE;
     }
 
-- 
2.30.2